package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:连接所有点的最小费用
 * <p>
 * User:Mr.Du
 * Date:2024/4/16
 * Time:16:06
 */
public class MinCostConnectPoints {

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        DisjointSetUnion dsu = new DisjointSetUnion(n);
        List<Edge> edges = new ArrayList<Edge>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.add(new Edge(dist(points, i, j), i, j));
            }
        }
        Collections.sort(edges, new Comparator<Edge>() {
            public int compare(Edge edge1, Edge edge2) {
                return edge1.len - edge2.len;
            }
        });
        int ret = 0, num = 1;
        for (Edge edge : edges) {
            int len = edge.len, x = edge.x, y = edge.y;
            if (dsu.unionSet(x, y)) {
                ret += len;
                num++;
                if (num == n) {
                    break;
                }
            }
        }
        return ret;
    }

    public int dist(int[][] points, int x, int y) {
        return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
    }
}

class DisjointSetUnion {
    int[] f;
    int[] rank;
    int n;

    public DisjointSetUnion(int n) {
        this.n = n;
        this.rank = new int[n];
        Arrays.fill(this.rank, 1);
        this.f = new int[n];
        for (int i = 0; i < n; i++) {
            this.f[i] = i;
        }
    }

    /**
     * 查找给定元素的根节点。
     *
     * @param x 要查找的元素。
     * @return 元素x的根节点。
     */
    public int find(int x) {
        // 如果当前元素的父节点是它自身，则返回该元素自身，否则递归查找其父节点的父节点，直到找到根节点
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

    /**
     * 将两个集合合并。
     * 该函数首先查找x和y所属的集合，然后将这两个集合合并。
     * 如果x和y已经在同一个集合中，函数不进行任何操作并返回false。
     * 如果成功合并两个集合，则返回true。
     *
     * @param x 第一个元素的标识符。
     * @param y 第二个元素的标识符。
     * @return 如果成功合并两个集合，返回true；如果x和y已经在同一个集合中，返回false。
     */
    public boolean unionSet(int x, int y) {
        int fx = find(x), fy = find(y); // 查找x和y所属的集合。
        if (fx == fy) {
            return false; // 如果x和y已经在同一个集合中，直接返回false。
        }
        if (rank[fx] < rank[fy]) { // 如果fx所在集合的秩小于fy所在集合的秩，交换它们以确保fx的秩不小于fy的秩。
            int temp = fx;
            fx = fy;
            fy = temp;
        }
        rank[fx] += rank[fy]; // 更新合并后集合的秩。
        f[fy] = fx; // 将fy所在集合指向fx所在集合，完成合并。
        return true;
    }

}

class Edge {
    int len, x, y;

    public Edge(int len, int x, int y) {
        this.len = len;
        this.x = x;
        this.y = y;
    }
}
